package com.linyaonan.leetcode.medium._1358;

import java.util.HashMap;
import java.util.Map;

/**
 * 给你一个字符串 s ，它只包含三种字符 a, b 和 c 。
 *
 * 请你返回 a，b 和 c 都 至少 出现过一次的子字符串数目。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "abcabc"
 * 输出：10
 * 解释：包含 a，b 和 c 各至少一次的子字符串为 "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" 和 "abc" (相同字符串算多次)。
 * 示例 2：
 *
 * 输入：s = "aaacb"
 * 输出：3
 * 解释：包含 a，b 和 c 各至少一次的子字符串为 "aaacb", "aacb" 和 "acb" 。
 * 示例 3：
 *
 * 输入：s = "abc"
 * 输出：1
 *
 *
 * 提示：
 *
 * 3 <= s.length <= 5 x 10^4
 * s 只包含字符 a，b 和 c 。
 *
 * @author: Lin
 * @date: 2024/10/31
 */
public class NumberOfSubstringsContainingAllThreeCharacters {

    /**
     * 滑动窗口的思路，一旦已经出现了abc的全部字符，那么从该位置向后的所有情况也都均包含
     * @param s
     * @return
     */
    public int numberOfSubstrings(String s) {
        int l = 0;
        int r = 0;
        Map<Character, Integer> saved = new HashMap<>(4);
        int count = 0;

        while (l <= r && r < s.length()) {
            char current = s.charAt(r);
            saved.merge(current, 1, Integer::sum);
            while (saved.size() == 3) {
                count += (s.length() - r);
                char pre = s.charAt(l);
                if (saved.merge(pre, -1 ,Integer::sum) == 0) {
                    saved.remove(pre);
                }
                l++;
            }
            r++;
        }
        return count;
    }
}
